package com.fantastic.sort;

import java.util.Arrays;

/**
 * @author : fantastic
 * @date : 2024/5/15 16:46
 * @desc : this class for xxxxx
 **/
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {20, 10, 11, 14, 9, 9, 10, 13};
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));
    }

    public static int[] sort(int[] arr) {
        if (arr.length <= 1) {
            return arr;
        }
        int num = arr.length >> 1;
        int[] left = Arrays.copyOfRange(arr, 0, num);
        int[] right = Arrays.copyOfRange(arr, num, arr.length);
        return mergeSort(sort(left), sort(right));
    }

    public static int[] mergeSort(int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        int[] result = new int[left.length + right.length];

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        while (i < left.length) {
            result[k++] = left[i++];
        }
        while (j < right.length) {
            result[k++] = right[j++];
        }
        return result;
    }
}

